package 把二叉搜索树转换为累加树;

import 路径总和.Demo112;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 把二叉搜索树转换为累加树
 * @date 2022/11/12 16:35
 */
public class Demo538 {
    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(4);
        treeNode.left=new  TreeNode(1);
        treeNode.right=new TreeNode(6);
        treeNode.right.right=new TreeNode(7);
        treeNode.right.left=new TreeNode(5);
        treeNode.left.left=new TreeNode(0);
        treeNode.left.right=new TreeNode(2);
        treeNode.left.right.right=new TreeNode(3);
        treeNode.right.right.right=new TreeNode(8);
        TreeNode treeNode1 = convertBST(treeNode);
        System.out.println(treeNode1);

    }
    static  int sum=0;
    public static TreeNode convertBST(TreeNode root) {
        if(root==null){
            return null;
        }
        //二叉搜索树中序遍历结果是有序的，累加树只需要右中左遍历，数值累加即可
        convertBST(root.right);
        sum=sum+root.val;
        root.val=sum;
        convertBST(root.left);
        return root;
    }




    //Definition for a binary tree node.
    public static  class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}
